package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;

/**
 * 求无权图的联通分量
 *
 * @author initcap
 * @date Created in 1/20/19 5:34 PM.
 */
public class Components {

    /**
     * 图的引用
     */
    private Graph<Integer, Double> graph;
    /**
     * 记录联通分量个数
     */
    private int ccount;
    /**
     * 每个节点所对应的联通分量标记,记录dfs的过程中节点是否被访问-1为访问，其余相同数值代表联通
     */
    private int[] visited;

    /**
     * 构造函数, 求出无权图的联通分量
     *
     * @param graph
     */
    public Components(Graph graph) {

        // 算法初始化
        this.graph = graph;
        visited = new int[this.graph.nodeSize()];
        ccount = 0;
        for (int i = 0; i < this.graph.nodeSize(); i++) {
            visited[i] = -1;
        }

        // 求图的联通分量
        for (int i = 0; i < this.graph.nodeSize(); i++) {
            if (visited[i] == -1) {
                dfs(i, ccount);
                ccount++;
            }
        }
    }

    /**
     * 图的深度优先遍历
     *
     * @param v    顶点
     * @param ccid 联通分量标记值
     */
    void dfs(int v, int ccid) {

        visited[v] = ccid;
        for (int i : graph.adj(v)) {
            if (visited[i] == -1) {
                dfs(i, ccid);
            }
        }
    }

    /**
     * 返回图的联通分量个数
     *
     * @return
     */
    int count() {
        return ccount;
    }

    /**
     * 查询点v和点w是否联通
     *
     * @param v
     * @param w
     * @return
     */
    boolean isConnected(int v, int w) {
        graph.validateVertex(v, graph.nodeSize());
        graph.validateVertex(w, graph.nodeSize());
        return visited[v] == visited[w];
    }

}
